from collections import deque


# 定义图的类
class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

    def bfs(self, start_vertex):
        # 初始化访问标记数组
        visited = [False] * self.num_vertices
        # 使用队列来实现BFS
        queue = deque()

        # 标记起始节点为已访问，并加入队列
        visited[start_vertex] = True
        queue.append(start_vertex)

        while queue:
            # 从队列中取出一个节点
            current_vertex = queue.popleft()
            print(current_vertex, end=" ")

            # 遍历当前节点的所有邻居
            for neighbor in self.adj_list[current_vertex]:
                if not visited[neighbor]:
                    # 标记邻居为已访问，并加入队列
                    visited[neighbor] = True
                    queue.append(neighbor)


# 示例图的构建
num_vertices = 6
graph = Graph(num_vertices)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(1, 4)
graph.add_edge(2, 4)
graph.add_edge(3, 4)
graph.add_edge(3, 5)
graph.add_edge(4, 5)

# 从节点0开始进行BFS遍历
print("BFS traversal starting from vertex 0:")
graph.bfs(0)
